# coding:utf-8

from typing import List


class Solution:
    ans = []
    current = []
    used = []

    def dfs(self, candidates: List[int], target: int, ix: int) -> None:
        if ix == len(candidates):
            return
        if target == 0:
            self.ans.append(list(self.current))
            return

        for i in range(ix, len(candidates)):
            if  target-candidates[i] < 0:
                return
            if i > 0 and candidates[i] == candidates[i-1] and self.used[i-1] == False:
                    continue
            self.used[i] = True
            self.current.append(candidates[i])
            self.dfs(candidates,target-candidates[i],i+1)
            self.used[i] = False
            self.current.pop()
                

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.used = [0 for i in range(len(candidates))]
        candidates.sort()
        self.dfs(candidates, target, 0)
        return self.ans


if __name__ == "__main__":
    solu = Solution()
    print(solu.combinationSum2([10,1,2,7,6,1,5],8))
